Adjacency List: An Efficient Graph Storage Method, What Makes It Better Than Adjacency Matrix?
This article introduces the basic concepts of graphs and two core storage methods: the adjacency matrix and the adjacency list. A graph consists of vertices (e.g., social network users) and edges (e.g., friendship relationships). The adjacency matrix is a 2D array where 0/1 indicates whether there is an edge between vertices. It requires O(n²) space with n being the number of vertices, and checking an edge takes O(1) time. However, it wastes significant space for sparse graphs (few edges). The adjacency list maintains a neighbor list for each vertex (e.g., a user’s friend list), with space complexity O(n + e) where e is the number of edges, as it only stores actual edges. Checking an edge requires traversing the neighbor list (O(degree(i)) time, with degree(i) being the number of neighbors of vertex i), but traversing neighbors is more efficient in practice. A comparison shows that the adjacency list significantly outperforms the adjacency matrix in both space and time efficiency for sparse graphs (most practical scenarios). It is the mainstream storage method for graph problems (e.g., shortest path algorithms), offering better space saving and faster traversal.
Read MoreAdjacency Matrix: Another Representation Method for Graphs and a Comparison of Advantages and Disadvantages
An adjacency matrix is a fundamental representation of a graph, essentially an n×n two-dimensional array where rows and columns correspond to the vertices of the graph, and element values indicate the existence or weight of edges between vertices. In an undirected graph, the value 1 represents the presence of an edge, and 0 represents its absence; in a weighted graph, the actual weight value is directly stored. Its advantages include: first, checking the existence of an edge takes only O(1) time, and calculating vertex degrees is efficient (for undirected graphs, it is the sum of a row, while for directed graphs, rows and columns correspond to out-degrees and in-degrees respectively); second, it is suitable for dense graphs (with edge counts close to n²), has high space utilization, and is simple to implement, making it easy for beginners to understand. Disadvantages include: a space complexity of O(n²), which wastes significant space for sparse graphs; traversing adjacent vertices requires O(n) time, making it less efficient than adjacency lists; and insufficient flexibility for dynamically adjusting the number of edges. In summary, the adjacency matrix trades space for time. It is suitable for dense graphs or scenarios requiring frequent edge queries or degree calculations, but unsuitable for sparse graphs or scenarios requiring frequent traversal of adjacent vertices. It serves as a foundational tool for understanding graph structures.
Read More